The present disclosure relates to an associative memory, and more particularly to an associative memory that effectively realizes a k-nearest neighbors algorithm.
In recent years, applications requiring pattern matching typified by character recognition, image recognition, etc. have been attracting great attention. In particular, by realizing pattern matching on large scale integrated circuits (LSIs), pattern matching will become applicable to high-function applications such as artificial intelligence and mobile equipment in the future. Realization of this technology has therefore been receiving much attention.
In the pattern matching, there are “perfect matching search approach” of searching for a pattern completely matching with search data, and “most similar search approach” of searching for a pattern most similar to search data, through a plurality of pieces of reference data stored in a database.
The former search approach, using a content addressable memory (CAM), is used for realization of routing in IP address tables of network routers, caches of processors, etc. In order to make computers perform processing of such flexible searching and comparison as those performed by human brains, it is indispensable to realize the latter search approach, the most similar search approach. A memory having a function of realizing such flexible comparison is especially called an “associative memory.”
As an example of the associative memory, known is one where the most similar search is performed using Manhattan distance or Euclidean distance between search data and reference data (e.g., S. Sasaki et al., “Digital Associative Memory for Word-Parallel Manhattan-Distance-Based Vector Quantization,” ESSCIRC' 2012, 2012, pp. 185-188). Also known is an associative memory where k-nearest neighbors search is adopted (e.g., M. A. Abedin et al., “Realization of K-Nearest-Matches Search Capability in Fully-parallel Associative Memories,” IEICE Trans. on Fundamentals, vol. E90-A, No. 6, 2007, pp. 1240-1243).
A k-nearest neighbors algorithm is often used as a machine learning algorithm in the field of pattern recognition. The k-nearest neighbors algorithm has high reliability in pattern recognition. In the prior art, while the k-nearest neighbors search is adopted in associative memories, the k-nearest neighbors algorithm has not been effectively realized. In particular, the prior art has not reached the point of realizing pattern classification based on the k-nearest neighbors algorithm.
In relation to the above problem, the present inventors invented a k-nearest neighbors associative memory that can effectively realize the k-nearest neighbors algorithm, and disclosed the invented memory under PCT/JP2014/003809 (hereinafter referred to as prior application).